#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right)
    {
    }
};

class Solution 
{
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root == nullptr)
        {
            return nullptr;
        }
        if(root == p || root == q)
        {
            return root;
        }
        auto left = lowestCommonAncestor(root->left, p, q);
        auto right = lowestCommonAncestor(root->right, p, q);
        if(left == nullptr && right == nullptr)
        {
            return nullptr;
        }
        if(left == nullptr && right != nullptr)
        {
            return right;
        }
        if(left != nullptr && right == nullptr)
        {
            return left;
        }
        if(left != nullptr && right != nullptr)
        {
            return root;
        }
        return nullptr;
    }
};

// 辅助函数：从数组构建二叉树（层序遍历方式，-1表示null）
TreeNode *buildTreeFromArray(vector<int> &arr)
{
    if (arr.empty() || arr[0] == -1) return nullptr;

    TreeNode *root = new TreeNode(arr[0]);
    queue<TreeNode *> q;
    q.push(root);

    int i = 1;
    while (!q.empty() && i < arr.size())
    {
        TreeNode *node = q.front();
        q.pop();

        // 左子节点
        if (i < arr.size() && arr[i] != -1)
        {
            node->left = new TreeNode(arr[i]);
            q.push(node->left);
        }
        i++;

        // 右子节点
        if (i < arr.size() && arr[i] != -1)
        {
            node->right = new TreeNode(arr[i]);
            q.push(node->right);
        }
        i++;
    }

    return root;
}

// 辅助函数：根据值查找节点
TreeNode *findNodeByValue(TreeNode *root, int val)
{
    if (!root) return nullptr;
    if (root->val == val) return root;
    
    TreeNode *left = findNodeByValue(root->left, val);
    if (left) return left;
    
    return findNodeByValue(root->right, val);
}

// 辅助函数：层序遍历打印二叉树
void printTree(TreeNode *root)
{
    if (!root)
    {
        cout << "[]" << endl;
        return;
    }

    queue<TreeNode *> q;
    q.push(root);
    vector<string> result;

    while (!q.empty())
    {
        TreeNode *node = q.front();
        q.pop();

        if (node)
        {
            result.push_back(to_string(node->val));
            q.push(node->left);
            q.push(node->right);
        } else
        {
            result.push_back("null");
        }
    }

    // 移除末尾的null
    while (!result.empty() && result.back() == "null")
    {
        result.pop_back();
    }

    cout << "[";
    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i];
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode *root)
{
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main()
{
    Solution solution;

    cout << "=== LeetCode 236. 二叉树的最近公共祖先 测试案例 ===" << endl << endl;

    // 测试案例1：题目示例1
    cout << "测试案例1：" << endl;
    vector<int> tree1 = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4};
    TreeNode *root1 = buildTreeFromArray(tree1);
    TreeNode *p1 = findNodeByValue(root1, 5);
    TreeNode *q1 = findNodeByValue(root1, 1);

    cout << "输入: root = ";
    printTree(root1);
    cout << "      p = " << p1->val << ", q = " << q1->val << endl;

    TreeNode *result1 = solution.lowestCommonAncestor(root1, p1, q1);
    cout << "输出: " << result1->val << endl;
    cout << "期望: 3" << endl << endl;

    // 测试案例2：题目示例2
    cout << "测试案例2：" << endl;
    TreeNode *p2 = findNodeByValue(root1, 5);
    TreeNode *q2 = findNodeByValue(root1, 4);

    cout << "输入: root = ";
    printTree(root1);
    cout << "      p = " << p2->val << ", q = " << q2->val << endl;

    TreeNode *result2 = solution.lowestCommonAncestor(root1, p2, q2);
    cout << "输出: " << result2->val << endl;
    cout << "期望: 5" << endl << endl;

    // 测试案例3：题目示例3
    cout << "测试案例3：" << endl;
    vector<int> tree3 = {1, 2};
    TreeNode *root3 = buildTreeFromArray(tree3);
    TreeNode *p3 = findNodeByValue(root3, 1);
    TreeNode *q3 = findNodeByValue(root3, 2);

    cout << "输入: root = ";
    printTree(root3);
    cout << "      p = " << p3->val << ", q = " << q3->val << endl;

    TreeNode *result3 = solution.lowestCommonAncestor(root3, p3, q3);
    cout << "输出: " << result3->val << endl;
    cout << "期望: 1" << endl << endl;

    // 测试案例4：p和q在同一子树中
    cout << "测试案例4（p和q在同一子树中）：" << endl;
    TreeNode *p4 = findNodeByValue(root1, 6);
    TreeNode *q4 = findNodeByValue(root1, 7);

    cout << "输入: root = ";
    printTree(root1);
    cout << "      p = " << p4->val << ", q = " << q4->val << endl;

    TreeNode *result4 = solution.lowestCommonAncestor(root1, p4, q4);
    cout << "输出: " << result4->val << endl;
    cout << "期望: 5" << endl << endl;

    // 测试案例5：其中一个节点是另一个的祖先
    cout << "测试案例5（一个节点是另一个的祖先）：" << endl;
    TreeNode *p5 = findNodeByValue(root1, 2);
    TreeNode *q5 = findNodeByValue(root1, 7);

    cout << "输入: root = ";
    printTree(root1);
    cout << "      p = " << p5->val << ", q = " << q5->val << endl;

    TreeNode *result5 = solution.lowestCommonAncestor(root1, p5, q5);
    cout << "输出: " << result5->val << endl;
    cout << "期望: 2" << endl << endl;

    // 测试案例6：简单的三节点树
    cout << "测试案例6（简单的三节点树）：" << endl;
    vector<int> tree6 = {1, 2, 3};
    TreeNode *root6 = buildTreeFromArray(tree6);
    TreeNode *p6 = findNodeByValue(root6, 2);
    TreeNode *q6 = findNodeByValue(root6, 3);

    cout << "输入: root = ";
    printTree(root6);
    cout << "      p = " << p6->val << ", q = " << q6->val << endl;

    TreeNode *result6 = solution.lowestCommonAncestor(root6, p6, q6);
    cout << "输出: " << result6->val << endl;
    cout << "期望: 1" << endl << endl;

    // 测试案例7：较深的树
    cout << "测试案例7（较深的树）：" << endl;
    vector<int> tree7 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    TreeNode *root7 = buildTreeFromArray(tree7);
    TreeNode *p7 = findNodeByValue(root7, 8);
    TreeNode *q7 = findNodeByValue(root7, 9);

    cout << "输入: root = ";
    printTree(root7);
    cout << "      p = " << p7->val << ", q = " << q7->val << endl;

    TreeNode *result7 = solution.lowestCommonAncestor(root7, p7, q7);
    cout << "输出: " << result7->val << endl;
    cout << "期望: 4" << endl << endl;

    // 清理内存
    deleteTree(root1);
    deleteTree(root3);
    deleteTree(root6);
    deleteTree(root7);

    cout << "所有测试案例执行完毕！" << endl;

    return 0;
}